The acquisition of data and subsequent generation of computer models for real-world objects is of interest in many industries, for applications including architecture, physical plant design, entertainment applications (e.g., in movies and games), surveying, manufacturing quality control, medical imaging, and construction, as well as cartography and geography applications. In order to obtain accurate models of an object, as well as the area in which that object exists in the real world, it is necessary to take accurate measurements or samplings of surfaces that make up the object and any elements of the surrounding area. Historically, this sampling was carried out by surveyors, photogrammetrists, or technicians using techniques that provided samples at the rate of tens or hundreds per hour at most. Since the amount of data was relatively small, the data was easily dealt with in standard, off-the-shelf CAD programs or other modeling software.
Recent advances in technology such as LIDAR scanning technologies have resulted in the ability to collect billions of point samples on physical surfaces, over large areas, in a matter of hours. In a LIDAR process, a laser beam scans across a view that encompasses the structure of interest. The scanning device measures a large number of points that lie on surfaces visible in the scene. Each scan point has a measured location in 3D space, to within some measurement error, that typically is recorded relative to a point (x,y,z) in the local coordinate system of the scanner. The resulting collection of points is often referred to as one or more point clouds, where each point cloud can include points that lie on many different surfaces in the scanned view.
LIDAR systems are described, for example, in U.S. Pat. No. 5,988,862, filed Apr. 24, 1996, entitled “INTEGRATED SYSTEM FOR QUICKLY AND ACCURATELY IMAGING AND MODELING THREE DIMENSIONAL OBJECTS,” which is hereby incorporated herein by reference. An exemplary LIDAR system 100 shown in FIG. 1 utilizes a Field Digital Vision (FDV) module 102 that includes a scanning sensor for scanning an object 104, such as a building of a piece of machinery. The scanning sensor also can sense the position in three-dimensional space of selected points on the surface of the object 104. The FDV module 102 generates a point cloud 106 that represents the sensed positions of the selected points. The point cloud 106 also can represent other attributes of the sensed positions, such as reflectivity, surface color, and texture, where desired.
A control and processing station 108 interacts with the FDV 102 to provide control and targeting functions for the scanning sensor. In addition, the processing and control station 108 can utilize software to analyze groups of points in the point cloud 106 to generate a model of the object of interest 104. A user interface 116 allows a user to interact with the system, such as to view a two-dimensional (2D) representation of the three-dimensional (3D) point cloud, or to select a portion of that object to be viewed in higher detail as discussed elsewhere herein. The processing station can include any appropriate components, such as standard computer and/or processing components. The processing station also can have computer code in resident memory, on a local hard drive, or in a removable drive or other memory device, which can be programmed to the processing station or obtained from a computer program product such as a CD-ROM or download signal. The computer code can include instructions for interacting with the FDV and/or a user, and can include instructions for undertaking and completing any modeling and/or scanning process discussed, described, or suggested herein.
The FDV 102 can include a scanning laser system (LIDAR) 110 capable of scanning points of the object 104, and that generates a LIDAR data signal that precisely represents the position in 3D space of each scanned point. The LIDAR data signal for the groups of scanned points can collectively constitute the point cloud 106. In addition, a video system 112 can be provided, which in one embodiment includes both wide angle and narrow angle CCD cameras. The wide angle CCD camera can acquire a video image of the object 104 and provides to the control and processing station 108, through a control/interface module 114, a signal that represents the acquired video image.
The acquired video image can be displayed to a user through a user interface 116 of the control and processing station 108. Through the user interface 116, the user can select a portion of the image containing an object to be scanned. In response to user input, the control and processing station can provide a scanning control signal to the LIDAR 110 for controlling the portion of the surface of the object that should be scanned by the LIDAR. More particularly, the scanning control signal can be used to control an accurate and repeatable beam steering mechanism that steers a laser beam of the LIDAR 110. The narrow angle CCD camera of the video system 112 can capture the intensity of the laser returned from each laser impingement point, along with any desired texture and color information, and can provide this captured information to the control and processing station 108. The control and processing station can include a data processing system (e.g., a notebook computer or a graphics workstation) having special purpose software that, when executed, instructs the data processing system to perform the FDV 102 control and targeting functions, and also to perform the model generation functions discussed elsewhere herein. Once the object has been scanned and the data transferred to the control and processing station, the data and/or instructions relating to the data can be displayed to the user. Alternatively, the user can select instructions before or during the LIDAR scan. If multiple scans are taken, these data sets can be registered to form a single data set, for a total number of points less than about 40 million for current technology, or can be registered but left as separate data sets for point sets larger than 40 million points, in order to allow the data to be loaded into a computer for processing and/or analysis. Current computer systems can only handle about 10 million points efficiently, but can handle up to about 40 million points inefficiently through compression techniques. Large octrees can be used in volumetric representations to store an approximation of the actual scan points, but the actual scan points are not available for processing. This simplification of the data can result in a loss of information and/or accuracy, and can cause problems when attempting to query the data.
Current scanning technologies can achieve sampling rates of up to 1 million points per second, with an accuracy of a few millimeters. While these advances can greatly increase the accuracy and complexity of the generated models, the advances also come with problems such as how to store, visualize, manipulate, and/or extract models and measurements from very large amounts of data, particularly where the vast amount of data cannot simply be loaded into computer memory, measured, partitioned, and modeled. For instance, individual data sets used to contain less than a million points but now can contain over 200 million points. Further, instead of tens of scans being taken of a physical object or structure it is now common to have on the order of 300-400 scans, greatly increasing the amount of data to be processed. Aggregate sample sets then can have tens of billions of data points. Current software can only compose data sets up to about 40 million points. For larger scans or data sets, the data is left uncomposed, or is reprocessed off-line into pieces no larger than about 40 million points, so that individual pieces can be worked with separately. The inability to easily process the data as a coherent whole is further complicated by the fact that data acquired by such scanners must undergo a series of processing steps to be used meaningfully, including the capture, registration, and fitting of the data.
The need for multiple data sets arises from the fact that most sensors providing the samples can only measure or detect a portion of the desired scan area from a given position. This is analogous to trying to get a full view of a three dimensional object with a camera. If the object can be moved, then a number of pictures must be taken from the single camera location in order to capture the entire object. If the object cannot be moved, the user must take multiple pictures from several different angles in order to have all of the surfaces of the object appear in at least one picture. Similarly, with sensor applications such as LIDAR applications, the sensor must often be moved to multiple locations in order to sample all sides or surfaces in a given target area. Since the various positions of the sensor generally are not known to any degree of certainty, it is necessary to determine how the sets of sensor samples from each position relate to each other. Without the proper relation information, it is impossible to generate a full sample set forming a coherent model of the entire object. In order to relate the data sets, a registration process must be undergone. Registering the data from multiple views is difficult and time consuming, in part because known techniques for registering sets of samples to each other do not work well on huge sample sets. Further, registration often requires intelligent decimation of those sets before the registration can take place. Existing systems cannot rapidly compute those intelligent decimations to accelerate registration operations.
Once the data sets are registered, it would be most efficient for the user be able to consider the samples to be in the same coordinate system and work with the data as a single, coherent whole. Unfortunately, the combination of many sample sets is often massive in size, and existing software packages still leave the individual sample sets separate in order to keep the size of any given set manageable. This separation leads to difficulty in measurement and fitting operations, as the user must manually cut and recombine small pieces of the sample sets together before being able to perform operations on the desired data segments. Further, managing the hundreds of data sets that are captured using existing systems can be overwhelming, particularly where each individual set is larger than can fit in memory. The size of the data sets can be addressed somewhat through existing data compression techniques (which presently can compress a data set by about 10%), but attempting to do data compression for a set containing 40 million data points, for example, can cause problems with system stability.
Another function which is problematic in existing systems is the partitioning of large data sets into smaller, coherent parts, typically referred to as data subsets. Users presently need to create subsets in order to do operations such as fitting. For example, the points corresponding to a pipe in a plant must sometimes be partitioned out from the rest of the data points for the plant in order to allow a geometric fit, or to copy the points for the pipe to another model in order to perform more detailed operations. Existing systems cannot efficiently support subset operations on large data sets, as these systems must do work proportional to the size of the components being cut in order to make that cut, then require space proportional to the size of the subset in order to store that subset.